// 题目：https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=13&tqId=634&ru=%2Fpractice%2Fa861533d45854474ac791d90e447bafd&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 思路1：1.前序遍历-递归实现；2.前序遍历到叶子节点的时候，比较当前路径的和与期望值比较；
         //3.如果不是叶子节点，则继续遍历比较；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool FindPath(TreeNode* root, int cur_sum,int expect_sum) {
    
        if (root->left == nullptr && root->right == nullptr) {
            auto leaf_sum = root->val + cur_sum;
            if (leaf_sum == expect_sum) return true;
            return false;
        } 

        bool res1 = false;
        if (root->left) {
           res1 = FindPath(root->left,root->val+cur_sum,expect_sum);
        } 

        bool res2 = false;
        if (root->right) {
            res2 = FindPath(root->right,root->val+cur_sum,expect_sum);
        }
        return res1||res2;
    }
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if (root == nullptr) return false;
        return FindPath(root,0,sum);
    }
};